The present invention relates to methods for improving data-retrieval times from a non-volatile storage device in which a cache memory is used for preloading a data segment before the data segment is loaded into a host system. Retrieved data (i.e. data which is requested by the host system) can be divided into ordered data (i.e. data that is arranged in a known and/or “predictable” sequence) and random data. The present invention focuses on retrieving ordered data from storage devices.
Data-retrieval operations from a storage device (e.g. a magnetic-tape recorder) are divided into two main sub-operations:                (1) an internal storage-device data-retrieval stage (hereinafter referred to as a “pre-loading stage”), which occurs upon a host-system request, involves the storage device's internal controller searching for the specific data, and preparing the data to be read by the host system. It is noted that the data is not delivered to the host system during the pre-loading stage.        (2) a host-system data-retrieval stage (hereinafter referred to as a “loading stage”), which occurs when the pre-loading stage is completed, involves the storage device notifying the host system that the data is ready to be read by the host system. Such notification can occur in two ways, such as by answering a host-system question as to whether the data is ready or not, or by invoking an interrupt to the host system, signaling that the data is ready.        
Clearly, such data-retrieval operations, typical to all storage devices in the prior art, have a built-in latency which is the time needed for the first sub-operation. This latency does not disturb the host system, and is hardly noticed if the time to process one segment of data is much longer than this latency. However, in some data-retrieval operations (especially in streaming processes such as loading JPEG and MPEG data, for example), the processing time is very short, and the latency of waiting for the storage device to complete the initial pre-loading stage becomes a problem. Moreover, in some applications, it is important that the data in storage be available on demand (e.g. utilizes a “demand-paging mechanism”).
It is important to note that proxy servers and cache storage systems known in the prior art do not solve the need described herein, as they are probabilistic and provide faster access based only on considerations that are external to the data itself (e.g. history of retrieval, availability of sectors, and a priori knowledge about future retrieval). The prior art fails to improve the loading time of an arbitrarily-selected data file using any type of predictive approach.
It would be desirable to have methods for predicting with a high probability of success which data segments will be subsequently loaded from a storage device. By applying such a prediction, and preparing the predicted data segment, such systems can save time and increase the efficiency of data retrieval.
It is noted that there are prior-art systems that cache a plurality of data segments for reducing the time of the reading process (e.g. a hard-disk drive that reads all the available sectors upon one revolution of the disk). Such prior art does not solve the need described above, as it applies only to contiguous data objects and to the amount of sectors that can be read in one revolution of the disk.